package Algorithm;

import Structure.Edge;
import Structure.Graph;
import Structure.GraphGenerator;
import Structure.Node;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;


/**
 * @Author: ylc
 * @Description:Dijkstra算法
 * @Date Created in 2022-06-07 19:30
 */
public class Dijkstra {
    public static HashMap<Node, Integer> dijkstra1(Node head) {
        // head出发到所有点的最小距离
        // key:从head到key
        // value:从head出发到key的距离
        HashMap<Node, Integer> distanceMap = new HashMap<>();
        distanceMap.put(head, 0);
        // 已经确定最小距离的节点
        HashSet<Node> selectedNodes = new HashSet<>();

        Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        while (minNode != null) {
            int distance = distanceMap.get(minNode);
            for (Edge edge :
                    minNode.edges) {
                Node toNode = edge.to;
                if (!distanceMap.containsKey(toNode)) {
                    distanceMap.put(toNode, distance + edge.weight);
                }
                distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));
            }
            selectedNodes.add(minNode);
            minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        }
        return distanceMap;
    }

    public static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes) {
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for (Map.Entry<Node, Integer> entry :
                distanceMap.entrySet()) {
            Node node = entry.getKey();
            int distance = entry.getValue();
            if (!touchedNodes.contains(node) && distance < minDistance) {
                minNode = node;
                minDistance = distance;
            }
        }
        return minNode;
    }
    public static void main(String[] args) {
        Graph graph = create();
        Map<Node, Integer> map = dijkstra1(graph.nodes.get(1));
        for (Node node :
                map.keySet()) {
            System.out.println(node.value + " = " + map.get(node));
        }
    }
    public static Graph create(){
        int[][] arr = {
                {6,1,2},{6,2,1},
                {1,1,3},{1,3,1},
                {5,1,4},{5,4,1},
                {5,2,3},{5,3,2},
                {5,3,4},{5,4,3},
                {3,2,5},{3,5,2},
                {6,3,5},{6,5,3},
                {4,3,6},{4,6,3},
                {2,4,6},{2,6,4},
                {6,5,6},{6,6,5},
        };

        return GraphGenerator.generateGraph(arr);
    }
}
